package top.truism.stack;

import java.util.Stack;

/**
 * 单调栈结构
 *
 */
public class MonotonousStack {

    /**
     * 暴力解法
     * @param arr
     * @param <T>
     */
    public static <T extends Comparable<T>> int[][] forceSolution(T[] arr) {
        int[][] result = new int[arr.length][2];
        for (int i = 0; i < arr.length; i++) {
            T temp = arr[i];
            int[] res = new int[2];
            int leftLessIndex = -1;
            int rightLessIndex = -1;
            // 确定左索引
            int cur = i - 1;
            while (cur >= 0) {
                if(arr[cur].compareTo(temp) < 0) {
                    leftLessIndex = cur;
                    break;
                }else {
                    cur--;
                }
            }
            res[0] = leftLessIndex;
            // 确定右索引
            cur = i + 1;
            while (cur < arr.length) {
                if(arr[cur].compareTo(temp) < 0) {
                    rightLessIndex = cur;
                    break;
                }else {
                    cur++;
                }
            }
            res[1] = rightLessIndex;

            result[i] = res;
        }
        return result;
    }

    /**
     * 利用单调栈解决
     * 栈中保存着元素从栈顶到栈底从大到小的索引
     *
     * @param <T>
     * @return
     */
    public static <T extends Comparable<T>> int[][] soluteByMonotonousStack(T[] arr) {
        int[][] result = new int[arr.length][2];
        Stack<Integer> stack = new Stack<>();

        for (int i = 0; i < arr.length; i++) {
            T temp = arr[i];
            while (!stack.isEmpty() && arr[stack.peek()].compareTo(temp) > 0) {
                int popIndex = stack.pop();
                int leftLessIndex = stack.isEmpty() ? -1 : stack.peek();
                result[popIndex] = new int[] {leftLessIndex, i};
            }
            stack.push(i);
        }
        while (!stack.isEmpty()) {
            int popIndex = stack.pop();
            int leftLessIndex = stack.isEmpty() ? -1 : stack.peek();
            result[popIndex] = new int[] {leftLessIndex, -1};
        }
        return result;
    }

}
